package gold.digger;

import gold.vo.TreeNode;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC993 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public boolean isCousins(TreeNode root, int x, int y) {
            return isCousinsPart(root, x, y) || isCousinsPart(root, y, x);
        }

        public boolean isCousinsPart(TreeNode root, int x, int y) {
            Deque<TreeNode> queue = new LinkedList<>();
            queue.push(root);

            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode cur = queue.pollFirst();
                    if (cur.val == x) {
                        for (int j = i + 1; j < size; j++) {
                            if (queue.pollFirst().val == y) return true;
                        }
                        return false;
                    } else {
                        if (null != cur.left && null != cur.right && cur.left.val == x && cur.right.val == y)
                            return false;
                        if (null != cur.left) queue.offerLast(cur.left);
                        if (null != cur.right) queue.offerLast(cur.right);
                    }
                }
            }

            return false;
        }
    }

    public void run() {
        Solution solution = new Solution();
        TreeNode root = TreeNode.createTree("[1,2,3,null,4]");
        System.out.println(solution.isCousins(root, 2, 3));
    }

    public static void main(String[] args) throws Exception {
        LC993 an = new LC993();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
